"""
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。
你需要让组成和的完全平方数的个数最少。
"""


class Solution(object):
    def numSquares(self, n):
        # square_nums = [i ** 2 for i in range(1, int(n ** 0.5) + 1)]
        #
        # def minNumSquares(k):
        #     """ recursive solution """
        #     # bottom cases: find a square number
        #     if k in square_nums:
        #         return 1
        #     min_num = float('inf')
        #
        #     # Find the minimal value among all possible solutions
        #     for square in square_nums:
        #         if k < square:
        #             break
        #         new_num = minNumSquares(k - square) + 1
        #         min_num = min(min_num, new_num)
        #     return min_num
        #
        # return minNumSquares(n)

        m = int(n ** 0.5)
        dp = list(range(n + 1))
        for i in range(1, m):
            cur = (i + 1) ** 2
            for j in range(cur, n + 1):
                dp[j] = min(dp[j], dp[j - cur] + 1)
        return dp[-1]
